package com.cqs.leetcode.tree;

import com.cqs.leetcode.TreeNode;

import java.util.*;

/**
 * @author lixiaowen
 * @create 2019-12-09
 */
public class PathSumII_113 {




    /**
     * 递归调用
     * @param root
     * @param sum
     * @return
     */
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        //DFS -- preorder
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        pathSum(root, sum, result, path);
        return result;
    }

    /**
     *  求路径之和
     *
     * @param root 当前子树的根节点
     * @param sum  当前子树的根节点到叶子结点的路径期望和
     * @param result 结果列表
     * @param path 某条路径已经参与计算的结点
     */
    private void pathSum(TreeNode root, int sum, List<List<Integer>> result, List<Integer> path) {
        if (root == null) return;
        //当前子树根节点 参与计算
        path.add(root.val);
        //修改期待值
        sum -= root.val;
        //叶子结点
        if (root.left == null && root.right == null) {
            if (sum == 0) {
                //符合要求，加入到结果集。注意这里的是拷贝
                result.add(new ArrayList<>(path));
            }
        } else {
            // 递归处理左子树
            if (root.left != null) {
                pathSum(root.left, sum, result, path);
            }
            // 递归处理右子树
            if (root.right != null) {
                pathSum(root.right, sum, result, path);
            }
        }
        //root结点不参与计算的分支。 还原path的状态。因为sum是字面量，不用还原。
        path.remove(path.size() - 1);
    }
}
